package com.algorithms.contests;

import java.util.Vector;

public class BitTCO2006
{
	static int dp[]=new int[1 << 18];

	int howMany(String[] mat)
	{
	    int N = mat.length;
	    int N2 = 1 << N;
	    dp[0] = 0;
	    for (int i = 1; i < N2; i++)
	    {
	        int bot = i & ~(i - 1);
	        int use = countOfTrailingZeros(bot);
	        dp[i] = dp[i ^ bot];
	        for (int j = use + 1; j < N; j++)
	            if ( (i&1<<j) !=0 && mat[use].charAt(j)== 'Y')
	                dp[i] = max(dp[i], dp[i ^ bot ^ (1 << j)] + 2);
	    }
	    return dp[N2 - 1];
	}
	
	private void debug(Object... obj)
	{
		System.out.println(obj);
	}
	private int max(int num1,int num2)
	{
		if(num1>num2)
			return num1;
		else
			return num2;
	}
	
	private int countOfTrailingZeros(int num)
	{
		int count=0;
		while((num&1<<count) !=0)
				{
				count++;
				}
		return count-1;
	}
	
	public static void main(String[] args)
	{
		String[] mat =new String[]
		                         {
				"NYYYY",
				"YNNNN",
				"YNNNN",
				"YNNNN",
				"YNNNN"
				};
		BitTCO2006 bitTCS2006= new BitTCO2006();
		System.out.println(bitTCS2006.howMany(mat));
		
	}
}
